import numpy as np
#5 states represent good quality times
state_index=5#0 F 1 2 3
state_discription=[0,1,2,3,4]
#transition matrix
# markov_transition_matrix=np.array([[0,2/3,1/3,0,0],
#                                     [1,0,0,0,0],
#                                     [0,2/3,0,1/3,0],
#                                     [0,2/3,0,0,1/3],
#                                     [0,0,0,0,1]])
#legendary444 0 1 F 2 3
markov_transition_matrix=np.array([[0,1,0,0,0],
                                    [0,0,2/3,1/3,0],
                                    [1,0,0,0,0],
                                    [0,0,2/3,0,1/3],
                                    [0,0,0,0,1]])


initial_state=np.array([1,0,0,0,0])
#myth cost
# cost_matrix=np.full((5,5),9)

# cost_matrix[1]=0

# cost_matrix[4]=0

#origin cost /#legend cost
cost_matrix=np.full((5,5),12)

cost_matrix[4]=0
cost_matrix[1]=0


#cost success table
table={}

#mcmc test create sequence
def mcmc_sample(P,initial_state,step):
    state_sequence=[np.random.choice(state_discription,p=initial_state)]
    for _ in range(step):
        current_state=state_sequence[-1]
        next_state=np.random.choice(state_discription,p=P[current_state])
        state_sequence.append(next_state)
        if(next_state==4):
            break
    return state_sequence
#create hash fre table
def create_cost_table(times):
    frequency_table={}
    for value in times.values():
        if value in frequency_table:
            frequency_table[value]+=1
        else :
            frequency_table[value]=1
    return frequency_table

#the initial N times success proportion in all situations 
def the_initial_N_pro(fre_table,N):
    #sum_cost=sum(fre_table.values())
    sum_cost_times=trial_time
    initial_N_times=0
    for i in range(N+1):
        if i in fre_table.keys():
            initial_N_times+=fre_table[i]
    initial_N_proportion=round(initial_N_times/sum_cost_times*100,3)
    return initial_N_proportion

def get_the_cost_of_proportion(fre_table,proportion):
    fre_table_sorted=sorted(fre_table.values())
    sum_cost_times=trial_time
    N_time=round(proportion*sum_cost_times/100)
    return fre_table_sorted[N_time]
    
        
total_cost=0
total_times=0
trial_time=30000

#experiment of trial times  
for j in range(trial_time):
    state_sequence=mcmc_sample(markov_transition_matrix,initial_state,step=1000)
    total_times+=len(state_sequence)-1
    #table[j]=len(state_sequence)
    current_ex_cost=0
    for i in range(len(state_sequence)-1):
        current_ex_cost+=cost_matrix[state_sequence[i]][state_sequence[i+1]]
    table[j]=int(current_ex_cost)
    total_cost+=current_ex_cost

expected_cost=total_cost/(trial_time)
expected_times=round(total_times/trial_time,3)
cost_table=create_cost_table(table)


#final state evaluate
state_dist=initial_state
for i in range(0,1000):#1000 times experiment
    while True:
        new_dist=state_dist @ markov_transition_matrix
        if np.allclose(new_dist,state_dist,rtol=1e-4,atol=1e-4):
            break
        state_dist=new_dist

initial_cost_N=200
initial_cost_N_2=500
initial_cost_N_3=1000
proportion=the_initial_N_pro(cost_table,initial_cost_N)  
proportion_2=the_initial_N_pro(cost_table,initial_cost_N_2)  
proportion_3=the_initial_N_pro(cost_table,initial_cost_N_3)

proportion_to_cost=80
cost_of_pro=get_the_cost_of_proportion(table,proportion_to_cost)  
print(f"final state probability is :{state_dist}")
print(f"the expected cost is :{expected_cost}")
print(f"the expected times is :{expected_times}")
print(f"the initial {initial_cost_N} cost success proportion is :{proportion}%")
print(f"the initial {initial_cost_N_2} cost success proportion is :{proportion_2}%")
print(f"the initial {initial_cost_N_3} cost success proportion is :{proportion_3}%")
print(f"the {proportion_to_cost}% success needs less than {cost_of_pro} cost")
